package class07


/*
	给定两个数组arrx和arry，长度都是N。代表二维平面上有N个点，第i个点的x坐标
	和y坐标分别为arr[i]和arr[j]，返回一条直线最多能穿过多少个点?

	【算法流程】
		1. 遍历所有的点
		2. 记录每个点可以经过的最多的点情况，具体如下
			2.a 记录共x轴的点的数量
			2.b 记录共y轴的点的数量
			3.c 记录同斜率的点的数量
			3.d 记录位置相同的点的数量
		3. 求出最多的点：max(a,b,c) + d

	【难点】：
			如何表示斜率不会精度缺失?
			1. 采用字符表示如：1_3 表示 1/3
			2. 采用map表示如：{1:{3: count}} 表示斜率为1/3
			3. 对斜率的正负需要有统一的规定，统一放分母或者统一放分子
*/
type Point struct {
	x int
	y int
}

func MaxPoints(points []Point) int {
	var slopeMap map[int]map[int]int
	var sameX, sameY, sameOne, div, ans, maxSameSlope int
	for i, p := range points {
		slopeMap = make(map[int]map[int]int )
		sameX, sameY, sameOne = 0, 0, 1
		for j :=i+1; j<len(points); j++ {
			x := p.x - points[j].x
			y := p.y - points[j].y
			if x == 0 && y == 0 {
				sameOne++
			} else if x == 0 {
				sameX++
			} else if y == 0 {
				sameY++
			} else {
				x, y = HandleXY(x, y) // 处理出现正负数的情况
				div = gcd(x, y)
				x, y = x/div, y/div
				if _, ok := slopeMap[x]; !ok {
					slopeMap[x] = make(map[int]int)
				}
				if _, ok := slopeMap[x][y]; !ok {
					slopeMap[x][y] = 0
				}
				slopeMap[x][y]++
				maxSameSlope = max(maxSameSlope, slopeMap[x][y])
			}
		}
		ans = max(ans, max(sameX, max(sameY, maxSameSlope)) + sameOne)
	}
	return ans
}

func HandleXY(x, y int) (int, int){
	if x*y > 0 && x < 0 {
		return -x, -y
	} else if x*y < 0 && x < 0 {
		return -x, -y
	}
	return x, y
}